package com.lyj.sc.paixu;

import java.util.Arrays;

/**
 * @Author: liyangjing
 * @Date: 2022/05/03/11:45
 * @Description:
 */
public class HeapSort2 {

    public static void main(String[] args) {
        //堆排序原理：堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
        //大顶堆：arr[i]>=arr[i*2+1]&&arr[i]>=arr[i*2+2]
        //小顶堆：arr[i]<=arr[i*2+1]&&arr[i]<=arr[i*2+2]
        int[] arr = {4,21,5,86,74,12,57,42};

//        非叶子节点索引
        int startIndex = (arr.length-1)/2;
        for (int i =startIndex;i>=0;i--){
            toMaxheap(arr,arr.length,i);
        }
        for (int length = arr.length-1; length >= 0; length--) {
                int temp = arr[0];
                arr[0]=arr[length];
                arr[length]=temp;
                toMaxheap(arr,length,0);
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     *
     * @param arr   //要进行排序的数组
     * @param size  //要排序的范围
     * @param startIndex  //起始的索引位置
     */
    private static void toMaxheap(int[] arr, int size, int startIndex) {

        int leftNode = startIndex*2+1;
        int rightNode = startIndex*2+2;
        int maxNode = startIndex;
        if(leftNode<size && arr[leftNode]>arr[maxNode]){
            maxNode=leftNode;
        }
        if(rightNode<size && arr[rightNode]>arr[maxNode]){
            maxNode=rightNode;
        }
        if(maxNode!=startIndex){
            int temp =arr[maxNode];
            arr[maxNode] = arr[startIndex];
            arr[startIndex] = temp;
            toMaxheap(arr,size,maxNode);
        }
    }
}
